Aprenentatge d'Occam

En la teoria de l'aprenentatge computacional, l'aprenentatge d'Occam és un model d'aprenentatge algorítmic on l'objectiu de l'alumne és produir una representació sucinta de les dades d'entrenament rebudes. Això està estretament relacionat amb l'aprenentatge probablement aproximadament correcte (PAC), on l'aprenent és avaluat pel seu poder predictiu d'un conjunt de proves.

L'aprenentatge d'Occam implica l'aprenentatge de PAC, i per a una gran varietat de classes de conceptes, també és cert el contrari: l'aprenentatge de PAC implica l'aprenentatge d'Occam.

Occam Learning rep el nom de la navalla d'Occam, que és un principi que estableix que, tenint en compte que totes les altres coses són iguals, s'hauria d'afavorir una explicació més curta de les dades observades en lloc d'una explicació més llarga. La teoria de l'aprenentatge d'Occam és una justificació formal i matemàtica d'aquest principi. Va ser mostrat per primera vegada per Blumer, et al. que l'aprenentatge d'Occam implica l'aprenentatge PAC, que és el model estàndard d'aprenentatge en la teoria de l'aprenentatge computacional. En altres paraules, la parsimònia (de la hipòtesi de sortida) implica poder predictiu.

La concisió d'un concepte $c$ a classe de concepte ${\mathcal {C}}$ es pot expressar per la longitud $size(c)$ de la cadena de bits més curta que pot representar $c$ en ${\mathcal {C}}$. L'aprenentatge d'Occam connecta la concisió de la sortida d'un algorisme d'aprenentatge amb el seu poder predictiu sobre dades no vistes.

Deixar ${\mathcal {C}}$ i ${\mathcal {H}}$ ser classes de conceptes que contenen conceptes i hipòtesis objectiu respectivament. Després, per a constants $\alpha \geq 0$ i $0\leq \beta <1$, un algorisme d'aprenentatge $L$ és un $(\alpha ,\beta )$ -Algorisme d'Occam per ${\mathcal {C}}$ utilitzant ${\mathcal {H}}$ si, donat un conjunt $S=\{x_{1},\dots ,x_{m}\}$ de $m$ mostres etiquetades segons un concepte $c\in {\mathcal {C}}$, $L$ dona sortida a una hipòtesi $h\in {\mathcal {H}}$ de tal manera

• $h$ és coherent amb $c$ activat $S$ (això és, $h(x)=c(x),\forall x\in S$), i
• $size(h)\leq (n\cdot size(c))^{\alpha }m^{\beta }$

on $n$ és la longitud màxima de qualsevol mostra $x\in S$. Un algorisme d'Occam s'anomena eficient si s'executa en un polinomi de temps $n$, $m$, i $size(c).$ Diem una classe de conceptes ${\mathcal {C}}$ és Occam aprendre respecte a una classe d'hipòtesis ${\mathcal {H}}$ si existeix un algorisme Occam eficient per ${\mathcal {C}}$ utilitzant ${\mathcal {H}}.$